package Middle.WordsMaze;

/**
 * 题目要求：
 *     给定一个二维字符网格和一个单词，判断单词是否存在于网格中，
 *     单词可以由相邻单元格（水平或垂直相邻）的字母构成，
 *     同一个单元格内的字母在一个单词中不允许被重复使用。
 * 复杂度分析：
 *     时间复杂度：O(M×N×4^L)，其中M和N是网格的行列数，L是单词长度
 *     空间复杂度：O(L)（递归栈深度）加上O(M×N)（visited数组）
 */
public class WordsMaze_DFS {
    public static void main(String[] args) {
        char[][] grids = new char[][]{
                new char[]{'A', 'B', 'C', 'E'},
                new char[]{'S', 'F', 'C', 'S'},
                new char[]{'A', 'D', 'E', 'E'},
                new char[]{'H', 'E', 'R', 'N'},
                new char[]{'U', 'I', 'O', 'P'}
        };
        String target = "ABCCE";
        System.out.println(wordPuzzle(grids, target));
    }

    public static Boolean wordPuzzle(char[][] grids, String target) {
        if (grids == null ||grids.length == 0 || target.isEmpty()) {
            return false;
        }
        int m = grids.length;
        int n = grids[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(grids, target, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean dfs(char[][] grids, String word, boolean[][] visited, int row, int col, int index) {
        if (index == word.length()) {
            return true;
        }
        //边界判断
        boolean isBounding = row < 0 || row >= grids.length || col < 0 || col >= grids[row].length;
        //超出边界，或者已占用，或者不相等，都判断为失败
        if (isBounding || visited[row][col] || grids[row][col] != word.charAt(index)) {
            return false;
        }
        //把访问置为占用状态
        visited[row][col] = true;

        //
        boolean found = dfs(grids, word, visited, row + 1, col, index + 1) ||
                dfs(grids, word,visited, row, col + 1, index + 1) ||
                dfs(grids, word, visited, row - 1, col, index + 1) ||
                dfs(grids, word, visited, row, col - 1, index + 1);
        visited[row][col] = found;
        return found;
    }
}